package hash;

import javax.validation.constraints.Null;
import java.util.HashMap;
import java.util.Map;
import java.util.UUID;

class Node{
     public String  key;
     public Node next=null;
     public Integer hashcode;
     public String value;

    public Node(String key, Node next, Integer hashcode,String value) {
        this.key = key;
        this.next = next;
        this.hashcode = hashcode;
        this.value=value;
    }

    public Node() {
        this.key = "";
        this.next = null;
        this.hashcode = 0;
    }

    @Override
    public String toString() {
        return "Node{" +
                "key='" + key + '\'' +
                ", next=" + next +
                ", hashcode=" + hashcode +
                '}';
    }
}
public class Hash {

    public static int len=1000; //初始化数组的长度
    public static int NodeCount=0;//元素个数
    public static Node[] NodeArr=new Node[len];
    public static Node[] TempNewNodeArr=null; //用于扩容的数组
    public static int findLen=10; //寻址法寻多少个

    public static void main(String[] args) {

        Map<Integer,Integer> map=new HashMap<Integer, Integer>();

        int c=0;
        for (int i=0;i<len;i++){
            String key= UUID.randomUUID().toString();

             c= add(key,key);

        }

        for (int i=0;i<800;i++){
            String key= UUID.randomUUID().toString();

            c= add(key,key);

        }

        c =add("java","6666");
//        c =add("java","6666");
        c =add("java1","6666");


        dump();

        String value=get("java");

        System.out.println(value);
//            map.put(code,)
//        System.out.println(map.size());
}

    public static String  get(String key){
        int hashcode = Math.abs(key.hashCode() % len);

        Node node= NodeArr[hashcode];
        String value=null;
        Node curr=new Node();
        if (node !=null){  //找到而且有人
            curr=node;

            while (true){
                if (curr.key==key){ //直接找到
                    value=curr.value;
                    break;
                }else if (curr.next==null && curr.key!=key){ //下一个为空,而且当前还不等于下一个
                    break;
                }else if (curr.next!=null){ //下一个不为空直接 下一个循环
                    curr=curr.next;
                    continue;
                }else{
                    break;
                }
            }
        }

        if (value==null)
        { //没找到,用寻址法找

            boolean isFind=false;
            //寻址法
            for (int findIndex=hashcode+1;findIndex<hashcode+findLen;findIndex++){
                if (findIndex<len && NodeArr[findIndex]!=null && NodeArr[findIndex].key==key){  //找到了
                    isFind=true;
                    value=NodeArr[findIndex].value;
                    break;
                }
            }
        }

        return value;
    }

    public static void dump(){

        int count=0;
        for (int j=0;j<NodeArr.length;j++){
            System.out.println(NodeArr[j]);
            if (NodeArr[j]!=null){
                count++;
            }
        }

        System.out.println("元素个数"+NodeCount+"占的坑位有"+count+"坑容量"+NodeArr.length);

    }


    public static int add(String key, String value){
        int hashcode = Math.abs(key.hashCode() % len);

        Node node= NodeArr[hashcode];

        if (node ==null || key==node.key){  //找到坑没有人
            Node newNode=new Node(key,null,hashcode,value);
            NodeArr[hashcode]=newNode;
        }else{ //这个坑有人了
            Node newNode=new Node(key,null,hashcode,value);

            boolean isFind=false;
            //寻址法
            for (int findIndex=hashcode+1;findIndex<hashcode+findLen;findIndex++){
                if (findIndex<len && NodeArr[findIndex]==null){  //插在这
                    NodeArr[findIndex]=newNode;
                    isFind=true;
                    break;
                }
            }

            if (!isFind){ //如果后面10个都是满的
                node.next=newNode;
            }

        }
        NodeCount++;

        changeToBig();

        return NodeArr.length;
    }

    /**
     * 扩容变大
     */
    public static void changeToBig(){
        if (NodeCount>len){
            NodeCount=0;
            System.out.println("开始扩张");
            len=len*2;
            TempNewNodeArr=new Node[len];

            for (int i=0;i<NodeArr.length;i++){
                Node tempNode=NodeArr[i];
                if (tempNode==null){
                    continue;
                }
                toNewAdd(tempNode,len);

                while (true){
                    if (tempNode.next!= null){
                        tempNode=tempNode.next;
                        toNewAdd(tempNode,len);
                    }else{
                        break;
                    }
                }
            }

            NodeArr=TempNewNodeArr;
            TempNewNodeArr=null;
        }
    }

    public static void toNewAdd(Node node, int newLen){

        int hashcode = Math.abs(node.key.hashCode() % newLen);

        Node tempNode= TempNewNodeArr[hashcode];

        if (tempNode ==null || node.key==tempNode.key){  //找到坑没有人
            Node newNode=new Node(node.key,null,hashcode,node.value);
            TempNewNodeArr[hashcode]=newNode;
        }else{ //这个坑有人了

            boolean isFind=false;
            //寻址法
            for (int findIndex=hashcode+1;findIndex<hashcode+findLen;findIndex++){
                if (findIndex<len && TempNewNodeArr[findIndex]==null){  //插在这
                    TempNewNodeArr[findIndex]=node;
                    isFind=true;
                    break;
                }
            }

            if (!isFind){ //如果后面10个都是满的
                tempNode.next=node;
            }

        }
        NodeCount++;
    }


}
